package com.wkh.datastructure.BinaryTree;

import com.wkh.datastructure.stack.LinkedListStack;

public class TreeTraversal {
    public static void main(String[] args) {
        //创建二叉树
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4, null, null), new TreeNode(7)),
                new TreeNode(3,
                        new TreeNode(5, null, null),
                        new TreeNode(6, null, null)));
        /*preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);*/
        //创建自定义栈
        LinkedListStack<TreeNode> stack = new LinkedListStack<>(10);
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                System.out.print("去："+curr.value);
                //入栈
                stack.push(curr);
                curr = curr.left;
            }else{
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop){
                    pop = stack.pop();
                    System.out.print("回："+pop.value);
                }else{
                    curr = peek.right;
                }

            }
        }
    }

    /**
     * 前序遍历
     * @param node
     */
    static void preOrder(TreeNode node){
        if (node == null){
            return;
        }
        System.out.print(node.value+"\t");
        preOrder(node.left);
        preOrder(node.right);
    }
    /**
     * 中序遍历
     * @param node
     */
    static void inOrder(TreeNode node){
        if (node == null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.value+"\t");
        inOrder(node.right);
    }
    /**
     * 后序遍历
     * @param node
     */
    static void postOrder(TreeNode node){
        if (node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value+"\t");
    }
}
